﻿using System;

namespace Msngr
{
    class BinaryTree<T> where T : IComparable
    {
        private Node root;
        private int length;
        private int height;

        public int Length { get { return length; } }

        public int Height { get { return height; } }

        public class Node
        {
            public T data;
            public Node left;
            public Node right;
            public Node(T data) { this.data = data; }
        }

        public void Add(T data)
        {
            if (root == null) { root = new Node(data); }
            else RecursiveAdd(ref root, data);
            length++;
            height = CalculateHeight(root);
        }

        private void RecursiveAdd(ref Node node, T data)
        {
            if (data.CompareTo(node.data) <= 0)
            {
                if (node.left == null) node.left = new Node(data);
                else RecursiveAdd(ref node.left, data);
            }
            else
            {
                if (node.right == null) node.right = new Node(data);
                else RecursiveAdd(ref node.right, data);
            }
        }

        private int CalculateHeight(Node node)
        {
            if (node == null) return 0;
            return Math.Max(CalculateHeight(node.left), CalculateHeight(node.right)) + 1;
        }

        public void Remove(T data)
        {
            if (SearchAndDestroy(ref root, data)) length--;
        }

        private bool SearchAndDestroy(ref Node node, T data)
        {
            if (node.data.Equals(data))
            {
                if (node.left != null && node.right != null)
                {
                    Node tNode = node.right;
                    while (tNode.left != null)
                    {
                        tNode = tNode.left;
                    }
                    node.data = tNode.data;
                    SearchAndDestroy(ref node.right, node.data);
                    return true;
                }
                else if (node.left != null)
                {
                    node = node.left;
                    return true;
                }
                else
                {
                    node = node.right;
                    return true;
                }
            }
            else if ((data.CompareTo(node.data) <= 0) && node.left != null) SearchAndDestroy(ref node.left, data);
            else if (node.right != null) SearchAndDestroy(ref node.right, data);
            return false;
        }

        //TODO
        public bool HasData()
        {
            return false;
        }

        public void Clear()
        {
            root = null;
        }

        //Works?
        public void Optimize()
        {
            //BinaryTree<T> tempTree = new BinaryTree<T>();
            //LinkedList<T> tempList = CopyTreeToList(new LinkedList<T>(), root);
            //int newRootIndex = (int)tempList.Length / 2;
            //T newRootData = tempList.GetNodeAtIndex(newRootIndex).data;
            //tempTree.Add(newRootData);
            //tempList.Remove(newRootData);
            //for (int i = 0; i <= size; i++)
            //{
            //    if (tempList.GetNodeAtIndex(i) != null)
            //    {
            //        var tempNode = tempList.GetNodeAtIndex(i);
            //        tempTree.Add(tempNode.data);
            //    }
            //}
            //root = tempTree.root;
        }

        private LinkedList<T> CopyTreeToList(LinkedList<T> list, Node node)
        {
            if (node != null)
            {
                if (node.left != null) CopyTreeToList(list, node.left);
                list.AddAtBeggining(node.data);
                if (node.right != null) CopyTreeToList(list, node.right);
            }
            return list;
        }

        public override string ToString()
        {
            if (root == null) return String.Empty;
            string tree = TreeStringBuilder(root, 0);
            return tree.Substring(0, tree.Length - 1);
        }

        private string TreeStringBuilder(Node node, int layer)
        {
            string tree = String.Empty;
            if (node != null)
            {
                if (node.left != null) tree += TreeStringBuilder(node.left, layer + 1);
                tree += "<" + layer + ">" + node.data + " ";
                if (node.right != null) tree += TreeStringBuilder(node.right, layer + 1);
            }
            return tree;
        }
    }
}